package com.example.leetcode.treecode;
//链接：https://www.nowcoder.com/questionTerminal/8a19cbe657394eeaac2f6ea9b0f6fcf6?f=discussion
//来源：牛客网

public class Solution1 {
    public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
        TreeNode root = rebuild(pre,0,pre.length-1,in,0,in.length-1);
        return root;
    }
    //前序遍历{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}
    private TreeNode rebuild(int[] pre, int startPre, int endPre, int[] in, int startIn, int endIn) {

        if(startPre>endPre|| startIn>endIn)
            return null;
        // 根节点
        TreeNode root=new TreeNode(pre[startPre]);
        for (int i = startIn; i < endIn; i++) {
            if(pre[startPre]==in[i]){
                root.left=rebuild(pre, startPre+1, startPre+i-startIn, in, startIn, i);
                root.right=rebuild(pre, startPre+i-startIn+1, endPre, in, i+1, endIn);
                break;
            }
        }
        return  root;
    }

    //前序遍历{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}

}